#include "parser.h"

void Parser::insert(std::string non_term, std::string term, std::vector<std::string> shift){
    table_[{non_term, term}] = shift;
}

void Parser::init(int line_nums){
    // set line nums
    line_nums_ = line_nums;
    // 初始化符号栈
    stack_.emplace_back("CompUnit");
    // 构建非终结符号集
    non_terms_ = {"CompUnit", "PrimaryExpr", "UnaryExpr", "MulExpr", "AddExpr", "RelExpr", "LAndExpr", "LOrExpr", "Expr", "Param", "Params", "ParamStmt", "FuncDef", "else", "Block", "Stmt", "Stmts", "StmtTail", "CompUnit'", "MulExpr'", "AddExpr'", "RelExpr'", "LAndExpr'", "LOrExpr'", "NFPrimaryExpr", "NFUnaryExpr", "NFMulExpr", "NFAddExpr", "NFRelExpr", "NFLAndExpr", "NFLOrExpr", "NFExpr", "NFMulExpr'", "NFAddExpr'", "NFRelExpr'", "NFLAndExpr'", "NFLOrExpr'", "AcParam", "Exprs", "ExprStmt"};
    // 构建FIRST集
    first_["CompUnit"] = {"\'int\'", "\'void\'"};
    first_["PrimaryExpr"] = {"ID", "NUMBER", "\'(\'"};
    first_["UnaryExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["MulExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["AddExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["RelExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["LAndExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["LOrExpr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["Expr"] = {"ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["Param"] = {"\'int\'"};
    first_["FuncDef"] = {"\'int\'", "\'void\'"};
    first_["else"] = {"\'else\'", "ε"};
    first_["Block"] = {"\'{\'"};
    first_["Stmt"] = {"\'{\'", "\';\'", "\',\'", "ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'", "\'int\'", "\'if\'", "\'while\'", "\'break\'", "\'continue\'", "\'return\'"};
    first_["CompUnit'"] = {"\'int\'", "\'void\'"};
    first_["MulExpr'"] = {"\'*\'", "\'/\'", "\'%\'", "ε"};
    first_["AddExpr'"] = {"\'+\'", "\'-\'", "ε"};
    first_["RelExpr'"] = {"\'<\'", "\'>\'", "\'<=\'", "\'>=\'", "\'==\'", "\'!=\'", "ε"};
    first_["LAndExpr'"] = {"\'&&\'", "ε"};
    first_["LOrExpr'"] = {"\'||\'", "ε"};
    first_["NFPrimaryExpr"] = {"NUMBER", "\'(\'"};
    first_["NFUnaryExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFMulExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFAddExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFRelExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFLAndExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFLOrExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFExpr"] = {"NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'"};
    first_["NFMulExpr'"] = {"\'*\'", "\'/\'", "\'%\'", "ε"};
    first_["NFAddExpr'"] = {"\'+\'", "\'-\'", "ε"};
    first_["NFRelExpr'"] = {"\'<\'", "\'>\'", "\'<=\'", "\'>=\'", "\'==\'", "\'!=\'", "ε"};
    first_["NFLAndExpr'"] = {"\'&&\'", "ε"};
    first_["NFLOrExpr'"] = {"\'||\'", "ε"};
    first_["StmtTail"] = {"\'=\'", "\'(\'"};
    // 构建follow集
    follow_["Expr"] = {"\';\'", "\')\'", "\',\'"};
    follow_["Stmt"] = {"\'else\'", "\'{\'", "\';\'", "ID", "NUMBER", "\'(\'", "\'+\'", "\'-\'", "\'!\'", "\'int\'", "\'if\'", "\'while\'", "\'break\'", "\'continue\'", "\'return\'", "\'}\'"};
    follow_["CompUnit"] = {"$"};
    follow_["CompUnit'"] = {"$"};
    follow_["StmtTail"] = follow_["Expr"];
    follow_["else"] = follow_["Expr"];
    follow_["Block"] = follow_["Expr"];
    follow_["Block"].push_back("\'int\'");
    follow_["Block"].push_back("\'void\'");
    follow_["Block"].push_back("$");
    follow_["Stmts"] = {"\'}\'"};
    follow_["FuncDef"].push_back("\'int\'");
    follow_["FuncDef"].push_back("\'void\'");
    follow_["FuncDef"].push_back("$");
    follow_["Params"] = {"\')\'"};
    follow_["ParamStmt"] = {"\')\'"};
    follow_["Param"] = {"\',\'", "\')\'"};
    follow_["LOrExpr"] = follow_["Expr"];
    follow_["LOrExpr'"] = follow_["Expr"];
    follow_["LAndExpr"] = follow_["LOrExpr'"];
    for(auto &term : first_["LOrExpr'"]){
        follow_["LAndExpr"].push_back(term);
    }
    follow_["LAndExpr'"] = follow_["LAndExpr"];
    follow_["RelExpr"] = follow_["LAndExpr'"];
    for(auto &term : first_["LAndExpr'"]){
        follow_["RelExpr"].push_back(term);
    }
    follow_["RelExpr'"] = follow_["RelExpr"];
    follow_["AddExpr"] = follow_["RelExpr'"];
    for(auto &term : first_["RelExpr'"]){
        follow_["AddExpr"].push_back(term);
    }
    follow_["AddExpr'"] = follow_["AddExpr"];
    follow_["MulExpr"] = follow_["AddExpr'"];
    for(auto &term : first_["AddExpr'"]){
        follow_["MulExpr"].push_back(term);
    }
    follow_["MulExpr'"] = follow_["MulExpr"];
    follow_["UnaryExpr"] = follow_["MulExpr'"];
    for(auto &term : first_["MulExpr'"]){
        follow_["UnaryExpr"].push_back(term);
    }
    follow_["PrimaryExpr"] = follow_["UnaryExpr"];
    follow_["AcParam"] = follow_["PrimaryExpr"];
    follow_["AcParam"].push_back("\';\'");
    follow_["Exprs"] = {"\')\'"};
    follow_["ExprStmt"] = {"\')\'"};
    follow_["NFExpr"] = {"\';\'", "\')\'", "\',\'"};
    follow_["NFLOrExpr"] = follow_["NFExpr"];
    follow_["NFLOrExpr'"] = follow_["NFExpr"];
    follow_["NFLAndExpr"] = follow_["NFLOrExpr'"];
    for(auto &term : first_["NFLOrExpr'"]){
        follow_["NFLAndExpr"].push_back(term);
    }
    follow_["NFLAndExpr'"] = follow_["NFLAndExpr"];
    follow_["NFRelExpr"] = follow_["NFLAndExpr'"];
    for(auto &term : first_["NFLAndExpr'"]){
        follow_["NFRelExpr"].push_back(term);
    }
    follow_["NFRelExpr'"] = follow_["NFRelExpr"];
    follow_["NFAddExpr"] = follow_["NFRelExpr'"];
    for(auto &term : first_["NFRelExpr'"]){
        follow_["NFAddExpr"].push_back(term);
    }
    follow_["NFAddExpr'"] = follow_["NFAddExpr"];
    follow_["NFMulExpr"] = follow_["NFAddExpr'"];
    for(auto &term : first_["NFAddExpr'"]){
        follow_["NFMulExpr"].push_back(term);
    }
    follow_["NFMulExpr'"] = follow_["NFMulExpr"];
    follow_["NFUnaryExpr"] = follow_["NFMulExpr'"];
    for(auto &term : first_["NFMulExpr'"]){
        follow_["NFUnaryExpr"].push_back(term);
    }
    follow_["NFPrimaryExpr"] = follow_["NFUnaryExpr"];
    // 根据first集构建分析表
    // CompUnit
    for (auto &term : first_["FuncDef"])
    {
        insert("CompUnit", term, {"FuncDef", "CompUnit'"});
    }
    // CompUnit'
    for(auto &term : first_["FuncDef"]){
        insert("CompUnit'", term, {"FuncDef", "CompUnit'"});
    }
    insert("CompUnit'", "ε", {"ε"});
    // Stmt
    for(auto &term : first_["Block"]){
        insert("Stmt", term, {"Block"});
    }
    insert("Stmt", "\';\'", {"\';\'"});
    insert("Stmt", "\',\'", {"\',\'"});
    for(auto &term : first_["NFExpr"]){
        insert("Stmt", term, {"NFExpr"});
    }
    insert("Stmt", "ID", {"ID", "StmtTail"});
    insert("Stmt", "\'int\'", {"\'int\'", "ID", "\'=\'", "Expr"});
    insert("Stmt", "\'if\'", {"\'if\'", "\'(\'", "Expr", "\')\'", "Stmt", "else"});
    insert("Stmt", "\'while\'", {"\'while\'", "\'(\'", "Expr", "\')\'", "Stmt"});
    insert("Stmt", "\'break\'", {"\'break\'", });
    insert("Stmt", "\'continue\'", {"\'continue\'"});
    insert("Stmt", "\'return\'", {"\'return\'", "Expr"});
    // StmtTail
    insert("StmtTail", "\'=\'", {"\'=\'", "Expr"});
    insert("StmtTail", "\'(\'", {"AcParam"});
    // else
    insert("else", "\'else\'", {"\'else\'", "Stmt", "else"});
    insert("else", "ε", {"ε"});
    // Block
    insert("Block", "\'{\'", {"\'{\'", "Stmt", "Stmts", "\'}\'"});
    // Stmts
    for(auto &term : first_["Stmt"]){
        insert("Stmts", term, {"Stmt", "Stmts"});
    }
    insert("Stmts", "ε", {"ε"});
    // FuncDef
    insert("FuncDef", "\'int\'", {"\'int\'", "ID", "\'(\'", "Params", "\')\'", "Block"});
    insert("FuncDef", "\'void\'", {"\'void\'", "ID", "\'(\'", "Params", "\')\'", "Block"});
    // Params
    insert("Params", "\'int\'", {"Param", "ParamStmt"});
    insert("Params", "ε", {"ε"});
    // ParamStmt
    insert("ParamStmt", "\',\'", {"\',\'", "Param", "ParamStmt"});
    insert("ParamStmt", "ε", {"ε"});
    // Param
    insert("Param", "\'int\'", {"\'int\'", "ID"});
    // Expr
    for(auto &term : first_["LOrExpr"]){
        insert("Expr", term, {"LOrExpr"});
    }
    // LOrExpr
    for(auto &term : first_["LAndExpr"]){
        insert("LOrExpr", term, {"LAndExpr", "LOrExpr'"});
    }
    // LOrExpr'
    insert("LOrExpr'", "\'||\'", {"\'||\'", "LAndExpr", "LOrExpr'"});
    insert("LOrExpr'", "ε", {"ε"});
    // LAndExpr
    for(auto &term : first_["RelExpr"]){
        insert("LAndExpr", term, {"RelExpr", "LAndExpr'"});
    }
    // LAndExpr'
    insert("LAndExpr'", "\'&&\'", {"\'&&\'", "RelExpr", "LAndExpr'"});
    insert("LAndExpr'", "ε", {"ε"});
    // RelExpr
    for(auto &term : first_["AddExpr"]){
        insert("RelExpr", term, {"AddExpr", "RelExpr'"});
    }
    // RelExpr'
    for(auto &term : first_["RelExpr'"]){
        insert("RelExpr'", term, {term, "AddExpr", "RelExpr'"});
    }
    insert("RelExpr'", "ε", {"ε"});
    // AddExpr
    for(auto &term : first_["MulExpr"]){
        insert("AddExpr", term, {"MulExpr", "AddExpr'"});
    }
    // AddExpr'
    for(auto &term : first_["AddExpr'"]){
        insert("AddExpr'", term, {term, "MulExpr", "AddExpr'"});
    }
    insert("AddExpr''", "ε", {"ε"});
    // MulExpr
    for(auto &term : first_["UnaryExpr"]){
        insert("MulExpr", term, {"UnaryExpr", "MulExpr'"});
    }
    // MulExpr'
    for(auto &term : first_["MulExpr'"]){
        insert("MulExpr'", term, {term, "UnaryExpr", "MulExpr'"});
    }
    insert("MulExpr''", "ε", {"ε"});
    // UnaryExpr
    for(auto &term : first_["PrimaryExpr"]){
        insert("UnaryExpr", term, {"PrimaryExpr"});
    }
    insert("UnaryExpr", "\'+\'", {"\'+\'", "UnaryExpr"});
    insert("UnaryExpr", "\'-\'", {"\'-\'", "UnaryExpr"});
    insert("UnaryExpr", "\'!\'", {"\'!\'", "UnaryExpr"});
    // PrimaryExpr
    insert("PrimaryExpr", "ID", {"ID", "AcParam"});
    insert("PrimaryExpr", "NUMBER", {"NUMBER"});
    insert("PrimaryExpr", "\'(\'", {"\'(\'", "Expr", "\')\'"});
    // AcParam
    insert("AcParam", "\'(\'", {"\'(\'", "Exprs", "\')\'"});
    insert("AcParam", "ε", {"ε"});
    // Exprs
    for(auto &term : first_["Expr"]){
        insert("Exprs", term, {"Expr", "ExprStmt"});
    }
    // ExprStmt
    insert("ExprStmt", "\',\'", {"\',\'", "Expr", "ExprStmt"});
    insert("ExprStmt", "ε", {"ε"});
    // NFExpr
    for(auto &term : first_["NFLOrExpr"]){
        insert("NFExpr", term, {"NFLOrExpr"});
    }
    // NFLorExpr
    for(auto &term : first_["NFLAndExpr"]){
        insert("NFLorExpr", term, {"NFLAndExpr", "NFLOrExpr'"});
    }
    // NFLOrExpr'
    insert("NFLOrExpr'", "\'||\'", {"\'||\'", "NFLAndExpr", "NFLOrExpr'"});
    insert("NFLOrExpr'", "ε", {"ε"});
    // NFLAndExpr
    for(auto &term : first_["NFRelExpr"]){
        insert("NFLAndExpr", term, {"NFRelExpr", "NFLAndExpr'"});
    }
    // NFLAndExpr'
    insert("NFLAndExpr'", "\'&&\'", {"\'&&\'", "NFRelExpr", "NFLAndExpr'"});
    insert("NFLAndExpr'", "ε", {"ε"});
    // NFRelExpr
    for(auto &term : first_["NFAddExpr"]){
        insert("NFRelExpr", term, {"NFAddExpr", "NFRelExpr'"});
    }
    // NFRelExpr'
    for(auto &term : first_["NFRelExpr'"]){
        insert("NFRelExpr'", term, {term, "NFAddExpr", "NFRelExpr'"});
    }
    insert("NFRelExpr'", "ε", {"ε"});
    // NFAddExpr
    for(auto &term : first_["NFMulExpr"]){
        insert("NFAddExpr", term, {"NFMulExpr", "NFAddExpr'"});
    }
    // NFAddExpr'
    for(auto &term : first_["NFAddExpr'"]){
        insert("NFAddExpr'", term, {term, "NFMulExpr", "NFAddExpr'"});
    }
    insert("NFAddExpr''", "ε", {"ε"});
    // NFMulExpr
    for(auto &term : first_["NFUnaryExpr"]){
        insert("NFMulExpr", term, {"NFUnaryExpr", "NFMulExpr'"});
    }
    // NFMulExpr'
    for(auto &term : first_["NFMulExpr'"]){
        insert("NFMulExpr'", term, {term, "NFUnaryExpr", "NFMulExpr'"});
    }
    insert("NFMulExpr''", "ε", {"ε"});
    // NFUnaryExpr
    for(auto &term : first_["NFPrimaryExpr"]){
        insert("NFUnaryExpr", term, {"NFPrimaryExpr"});
    }
    insert("NFUnaryExpr", "\'+\'", {"\'+\'", "NFUnaryExpr"});
    insert("NFUnaryExpr", "\'-\'", {"\'-\'", "NFUnaryExpr"});
    insert("NFUnaryExpr", "\'!\'", {"\'!\'", "NFUnaryExpr"});
    // NFPrimaryExpr
    insert("NFPrimaryExpr", "ID", {"ID", "AcParam"});
    insert("NFPrimaryExpr", "NUMBER", {"NUMBER"});
    insert("NFPrimaryExpr", "\'(\'", {"\'(\'", "Expr", "\')\'"});
    // 根据follow构建分析表
    // CompUnit'
    insert("CompUnit'", "$", {"$"});
    // ExprStmt
    insert("ExprStmt", "\')\'", {"ε"});
    // Exprs
    insert("Exprs", "\')\'", {"ε"});
    // AcParam
    for(auto &term : first_["MulExpr'"]){
        insert("AcParam", term, {"ε"});
    }
    for(auto &term : first_["AddExpr'"]){
        insert("AcParam", term, {"ε"});
    }
    for(auto &term : first_["RelExpr'"]){
        insert("AcParam", term, {"ε"});
    }
    for(auto &term : first_["LAndExpr'"]){
        insert("AcParam", term, {"ε"});
    }
    for(auto &term : first_["LOrExpr'"]){
        insert("AcParam", term, {"ε"});
    }
    for(auto &term : follow_["Expr"]){
        insert("AcParam", term, {"ε"});
    }
    insert("AcParam", "\';\'", {"ε"});
    // MulExpr'
    for(auto &term : first_["AddExpr'"]){
        insert("MulExpr'", term, {"ε"});
    }
    for(auto &term : first_["RelExpr'"]){
        insert("MulExpr'", term, {"ε"});
    }
    for(auto &term : first_["LAndExpr'"]){
        insert("MulExpr'", term, {"ε"});
    }
    for(auto &term : first_["LOrExpr'"]){
        insert("MulExpr'", term, {"ε"});
    }
    for(auto &term : follow_["Expr"]){
        insert("MulExpr'", term, {"ε"});
    }
    // AddExpr'
    for(auto &term : first_["RelExpr'"]){
        insert("AddExpr'", term, {"ε"});
    }
    for(auto &term : first_["LAndExpr'"]){
        insert("AddExpr'", term, {"ε"});
    }
    for(auto &term : first_["LOrExpr'"]){
        insert("AddExpr'", term, {"ε"});
    }
    for(auto &term : follow_["Expr"]){
        insert("AddExpr'", term, {"ε"});
    }
    // RelExpr'
    for(auto &term : first_["LAndExpr'"]){
        insert("RelExpr'", term, {"ε"});
    }
    for(auto &term : first_["LOrExpr'"]){
        insert("RelExpr'", term, {"ε"});
    }
    for(auto &term : follow_["Expr"]){
        insert("RelExpr'", term, {"ε"});
    }
    // LAndExpr'
    for(auto &term : first_["LOrExpr'"]){
        insert("LAndExpr'", term, {"ε"});
    }
    for(auto &term : follow_["Expr"]){
        insert("LAndExpr'", term, {"ε"});
    }
    // LOrExpr'
    for(auto &term : follow_["Expr"]){
        insert("LOrExpr'", term, {"ε"});
    }
    // ParamStmt
    insert("ParamStmt", "\')\'", {"ε"});
    // Stmts
    insert("Stmts", "\'}\'", {"ε"});
    // else
    for(auto &term : follow_["Stmt"]){
        insert("else", term, {"ε"});
    }
    insert("else", "\'else\'", {"\'else\'", "Stmt"});
    // NFMulExpr'
    for(auto &term : first_["NFAddExpr'"]){
        insert("NFMulExpr'", term, {"ε"});
    }
    // NFAddExpr'
    for(auto &term : first_["NFRelExpr'"]){
        insert("NFAddExpr'", term, {"ε"});
    }
    // NFRelExpr'
    for(auto &term : first_["NFLAndExpr'"]){
        insert("NFRelExpr'", term, {"ε"});
    }
    // NFLAndExpr'
    for(auto &term : first_["NFLOrExpr'"]){
        insert("NFLAndExpr'", term, {"ε"});
    }
    // NFLOrExpr'
    for(auto &term : follow_["NFExpr"]){
        insert("NFLAndExpr'", term, {"ε"});
    }
    // Params
    insert("Params", "\')\'", {"ε"});
}

void Parser::analysis(std::vector<Token *> tokens, bool &result, std::vector<int> &faults){
    result = true;
    // 执行分析
    while(tokens.size() && stack_.size()){
        // 取token执行分析，如果栈顶和token相等，则出栈；否则推导
        if(stack_.back() == tokens[0]->type){
            stack_.pop_back();
            tokens.erase(tokens.begin());
            /*for(auto &non : stack_){
                std::cout << non << " ";
            }
            std::cout << std::endl;*/
        }
        else if(stack_.back() == "ε"){
            stack_.pop_back();
            /*for(auto &non : stack_){
                std::cout << non << " ";
            }
            std::cout << std::endl;*/
        }
        else{
            std::string non_term = stack_.back();
            if(table_[std::make_pair(non_term, tokens[0]->type)].empty()){
                result = false;
                if(faults.empty() || faults.back() != tokens[0]->line_num){
                    faults.emplace_back(tokens[0]->line_num);
                }
                // 错误调试
                /*std::cout << "Wrong!" << std::endl;
                for(auto &token : tokens){
                    std::cout << token->type;
                }
                std::cout << std::endl;*/
                // 错误恢复
                if(std::find(non_terms_.begin(), non_terms_.end(), stack_.back()) == non_terms_.end()){
                    stack_.pop_back();
                }
                else{
                    while(tokens.size() && std::find(follow_[stack_.back()].begin(), follow_[stack_.back()].end(), tokens[0]->type) == follow_[stack_.back()].end() && tokens[0] -> type != "\'{\'" && tokens[0] -> type != "\'}\'"){
                        tokens.erase(tokens.begin());
                    }
                    stack_.pop_back();
                }
            }
            else{
                std::vector<std::string> &non_terms = table_[std::make_pair(non_term, tokens[0]->type)];
                stack_.pop_back();
                stack_.insert(stack_.end(), non_terms.rbegin(), non_terms.rend());
                /*for(auto &non : stack_){
                    std::cout << non << " ";
                }
                std::cout << std::endl;*/
            }
        }
    }
    while(stack_.size() && table_[std::make_pair(stack_.back(), "ε")].size()){
        stack_.pop_back();
    }
    if(!stack_.empty() || !tokens.empty()){
        result = false;
        if(faults.empty() || faults.back() != line_nums_){
            faults.emplace_back(line_nums_);
        }
        //faults.emplace_back(last_line_num);
        /*for(auto &non : stack_){
            std::cout << non << " " << std::endl;
        }*/
    }
}

void Parser::print(bool &result, std::vector<int> &faults){
    // 打印语法分析结果
    if(result){
        std::cout << "accept" << std::endl;
    }
    else{
        std::cout << "reject" << std::endl;
        for(auto &line_num : faults){
            std::cout << line_num << std::endl;
        }
    }
}